Exercise 3 (Homework 1).
(Kleene star,
theory of languages)
Kleene Star – basic properties
Justify your answers to the following questions. Languages are taken over any fixed alphabet.
- Does the Kleene star distribute over concatenation of languages? That is, for every two languages L_1,L_2, does it hold that L_1^*L_2^*= (L_1L_2)^*? What if instead of “=” we only asked for “\subseteq” or “\supseteq”? What if we impose L_1=L_2, does it hold now? And what if, when L_1=L_2, instead of “=” we only asked for “\subseteq” or “\supseteq”?
- Do positive closures always induce nontrivial partitions? That is, for every two languages L_1,L_2, if L_1^+\cup L_2^+=\{a,b\}^+ and L_1^+\cap L_2^+=\emptyset, then either L_1=\emptyset or L_2=\emptyset.
- Does the Kleene star distribute over union of languages? That is, for every two languages L_1,L_2, does it hold that L_1^*\cup L_2^*= (L_1\cup L_2)^*? What if instead of “=” we only asked for “\subseteq” or “\supseteq”?
- Does the Kleene star distribute over intersection of languages? That is, for every two languages L_1,L_2, does it hold that L_1^*\cap L_2^*= (L_1\cap L_2)^*? What if instead of “=” we only asked for “\subseteq” or “\supseteq”?
- Is the Kleene star monotone w.r.t. inclusion? That is, for every two languages L_1,L_2, does L_1\subseteq L_2 imply L_1^*\subseteq L_2^*? Does the converse hold? That is, for every two languages L_1,L_2, does L_1^*\subseteq L_2^* imply L_1\subseteq L_2? What if L_1=\{a,b\} and L_2 is a language over \{a,b\}, does the converse hold in this special context?
- Chain of inclusions. Does it hold for every language L that \overline{L^*}\subseteq \overline{L}\subseteq \overline{L}^*? What if we reverse the inclusions? Does \overline{L^*}\supseteq \overline{L}\supseteq \overline{L}^* hold?
- Sufficient condition for distinct Kleene stars. Does L_1\cap L_2=\emptyset for two languages L_1, L_2 \not=\emptyset imply L_1^*\not=L_2^*?
- Where is the positive closure squared? Does L^+L^+\subseteq L^+ hold for every language L? Does the reverse inclusion L^+L^+\supseteq L^+ hold?